package 剑指Offer._4150;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/15 12:32
 * 把数字翻译成字符串
 * 算法：动态规划
 * dp[i] = dp[i - 1] + dp[i - 2]
 * 当前第 i 位单独翻译，可以得到的数量为 dp[i - 1]
 * 如果和前面一位一起翻译，可以得到的数量为 dp[i - 2]
 */
public class _46 {
    public static void main(String[] args) {
        System.out.println(new _46().translateNum_perfect(10258));
    }

    public int translateNum(int num) {
        String s = num + "";
        int len = s.length();
        int[] dp = new int[s.length() + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= len; i++) {
            int pre = s.charAt(i - 2) - '0';
            int cur = (s.charAt(i - 1) - '0') + pre * 10;
            if (pre != 0 && cur >= 0 && cur <= 25) dp[i] = dp[i - 1] + dp[i - 2];
            else dp[i] = dp[i - 1];
        }
        System.out.println(Arrays.toString(dp));
        return dp[s.length()];
    }

    /**
     * 由于每次遍历只与前两位有关，所以只需要两个变量即可
     * @param num
     * @return
     */
    public int translateNum_perfect(int num) {
        String s = num + "";
        int pre = 1, cur = 1;
        int len = s.length();
        for (int i = 1; i < len; i++) {
            int c = 10 * (s.charAt(i - 1) - '0') + s.charAt(i) - '0';
            int tmp = cur;
            if (c >= 10 && c <= 25) cur = cur + pre;
            pre = tmp;
        }
        return cur;
    }

}
